Dijkstra算法及证明

2024-03-07 20:34| 来源: 网络整理| 查看: 265

Dijkstra算法及证明问题描述

有n个点，m条边，求长度为n的数组dis，其中dis[i]表示从源点s到点i的最短距离

复杂度

O ( m l o g n ) O(mlogn) O(mlogn)

算法步骤令dis[s] = 0，其余节点的dis为无穷大,并将节点s入队找出一个未被标记的，dis[x]最小的节点x，然后标记节点x遍历x的所有相邻边(x,y,z)，若dis[y] > dis[x] + z，则使用dis[x]+z更新dis[y]并将节点y入队重复上述2 ~ 3步，直到所有节点都被标记算法证明

首先令被标记的点集为S，其余为T

每次从队列中拿出一个dis值最小的点，如果这个点未被标记就将其标记，这样可以保证源点s一定是经由S集中的点到达它，因为每次都是用S集中的点来更新到其他点的距离

其次，当一个点x从队列中拿出并将其标记时，它当前的dis值一定是最短距离，从以下两个方面证明：

如果到点x的最短路经过了集合T中的点，假设这条最短路的路径为s -> i1 -> i2 -> … -> y -> … -> x，其中y为这条路径上第一个T集合中的点，那么必然有dis[y] < dis[x]，这样按照算法的第2步应该拿出来的是y号点，故到x点的最短路径中的所有点一定是在集合S中由以上证明可知当前的dis[x]一定是经由S中的点到达的，假设点x是第k个加入集合S中的点，易知加入集合中的第一个点s的dis[x]是最短路径，由数学归纳法假设前k-1个点加入到集合中的时候dis值都是最短路径，因为加入集合时它们都更新了与之相邻的点的dis值，那么当拿出第k个点时dis值必然是最短距离，得证

(以上证明若有不严谨之处欢迎指出) 补充：想了想这不就是带优先队列的BFS吗，似乎根本不用证

例题

https://vjudge.net/problem/10951/origin

题意：有n个点m条边，问从1号点到n号点的最短距离

代码：

#include #define MAXN 105 #define MAXM 10005 #define INf 0x3f3f3f3f using namespace std; int n,m,tot,head[MAXN]; struct edge { int v,w,nxt; }edg[MAXM int id,w; node(){} node(int id,int w):id(id),w(w){} friend bool operator memset(dis,0x3f,sizeof(dis)); dis[s] = 0; while(!qu.empty()) qu.pop(); qu.push(node(s,0)); int u,v,w; while(!qu.empty()) { nod = qu.top(); qu.pop(); u = nod.id,w = nod.w; if(w != dis[u]) continue; for(int i = head[u];i != -1;i = edg[i].nxt) { v = edg[i].v,w = edg[i].w; if(dis[v] > dis[u] + w) { dis[v] = dis[u]+w; qu.push(node(v,dis[v])); } } } } inline void init() { tot = 0; memset(head,-1,sizeof(int)*(n+1)); } int main() { while(~scanf("%d%d",&n,&m) && n && m) { init(); int u,v,w; while(m--) { scanf("%d%d%d",&u,&v,&w); addedg(u,v,w); addedg(v,u,w); } dijkstra(1); printf("%d\n",dis[n]); } return 0; }

【本文地址】

公司简介

联系我们